সর্টিং অ্যালগরিদম (Sorting Algorithms)

সর্টিং (Sorting) হল একটি প্রক্রিয়া যার মাধ্যমে ডাটা (অথবা এলিমেন্ট) গুলো একটি নির্দিষ্ট অর্ডারে সাজানো হয়। সাধারণত ডাটা সাজানোর দুটি প্রধান অর্ডার থাকে:

1. অ্যাসেন্ডিং অর্ডার (Ascending Order): ছোট থেকে বড় (যেমন: 1, 2, 3, 4, ... )।
2. ডিসেন্ডিং অর্ডার (Descending Order): বড় থেকে ছোট (যেমন: 9, 8, 7, 6, ... )।

সর্টিং অ্যালগরিদমগুলি অত্যন্ত গুরুত্বপূর্ণ, কারণ এগুলি ডাটা প্রক্রিয়াকরণে ব্যবহৃত হয়, যেমন অনুসন্ধান (searching), ইনডেক্সিং, ডেটাবেস অপারেশন ইত্যাদি। জাভাতে কিছু জনপ্রিয় সর্টিং অ্যালগরিদমের মধ্যে রয়েছে বাবল সর্ট (Bubble Sort), ইনসার্ট সর্ট (Insertion Sort), সিলেকশন সর্ট (Selection Sort), মার্জ সর্ট (Merge Sort), এবং কুইক সর্ট (Quick Sort)।

নিচে এই অ্যালগরিদমগুলোর ব্যাখ্যা এবং তাদের জাভায় ইমপ্লিমেন্টেশন দেওয়া হলো।

1. বাবল সর্ট (Bubble Sort)

বাবল সর্ট একটি সরল সর্টিং অ্যালগরিদম যা এলিমেন্টগুলিকে একে একে পর্যালোচনা করে এবং তাদের যথাযথ অবস্থানে সুইচ করে। এটি সবচেয়ে ছোট এলিমেন্টটিকে প্রতিবার "বাবল আপ" করে বা সবচেয়ে বড় এলিমেন্টটিকে "বাবল ডাউন" করে।

সময় জটিলতা (Time Complexity): $O(n^2)$

জাভায় বাবল সর্ট:

public class BubbleSort {

    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // Traverse through all array elements
        for (int i = 0; i < n-1; i++) {
            // Last i elements are already sorted
            for (int j = 0; j < n-i-1; j++) {
                // Swap if the element found is greater than the next element
                if (arr[j] > arr[j+1]) {
                    // Swap temp and arr[i]
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        bubbleSort(arr);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

আউটপুট:

Sorted array: 
11 12 22 25 64 

2. ইনসার্ট সর্ট (Insertion Sort)

ইনসার্ট সর্ট একটি সরল সর্টিং অ্যালগরিদম, যেখানে এলিমেন্টগুলোকে একটি একে একে সাজানো হয়, একে একে এলিমেন্ট যুক্ত করা হয়। এটি গেম বা কার্ড খেলার সময় এক হাতে কার্ড সাজানোর মতো কাজ করে।

সময় জটিলতা (Time Complexity): $O(n^2)$

জাভায় ইনসার্ট সর্ট:

public class InsertionSort {

    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; ++i) {
            int key = arr[i];
            int j = i - 1;

            // Move elements of arr[0..i-1], that are greater than key,
            // to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

আউটপুট:

Sorted array: 
5 6 11 12 13 

3. সিলেকশন সর্ট (Selection Sort)

সিলেকশন সর্ট একটি সহজ সর্টিং অ্যালগরিদম, যেখানে পুরো অ্যারের মধ্যে সবচেয়ে ছোট বা সবচেয়ে বড় এলিমেন্ট খুঁজে বের করে তার সাথে প্রথম এলিমেন্টটি সোয়াপ করা হয়। এরপর পরবর্তী এলিমেন্টের জন্য এটি পুনরাবৃত্তি করা হয়।

সময় জটিলতা (Time Complexity): $O(n^2)$

জাভায় সিলেকশন সর্ট:

public class SelectionSort {

    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n-1; i++) {
            // Find the minimum element in unsorted array
            int minIdx = i;
            for (int j = i+1; j < n; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }
            }

            // Swap the found minimum element with the first element
            int temp = arr[minIdx];
            arr[minIdx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

আউটপুট:

Sorted array: 
11 12 22 25 64 

4. মার্জ সর্ট (Merge Sort)

মার্জ সর্ট একটি ডিভাইড এবং কনকার (Divide and Conquer) অ্যালগরিদম। এটি অ্যারেটিকে দুইটি সমান অংশে ভাগ করে এবং প্রতিটি অংশকে পুনরায় মার্জ সর্টে প্রয়োগ করে। শেষে দুইটি সাজানো অংশকে একত্রিত করে সমগ্র অ্যারে সাজানো হয়।

সময় জটিলতা (Time Complexity): $O(n \log n)$

জাভায় মার্জ সর্ট:

public class MergeSort {

    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            // Recursively divide the array into two halves
            mergeSort(arr, left, mid);
            mergeSort(arr, mid + 1, right);

            // Merge the two halves
            merge(arr, left, mid, right);
        }
    }

    private static void merge(int[] arr, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        // Copy data to temp arrays L[] and R[]
        System.arraycopy(arr, left, L, 0, n1);
        System.arraycopy(arr, mid + 1, R, 0, n2);

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements of L[], if any
        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        // Copy remaining elements of R[], if any
        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {38, 27, 43, 3, 9, 82, 10};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

আউটপুট:

Sorted array: 
3 9 10 27 38 43 82 

5. কুইক সর্ট (Quick Sort)

কুইক সর্ট আরেকটি ডিভাইড এবং কনকার অ্যালগরিদম, যেখানে পিভট নির্বাচন করা হয় এবং তাকে এমন একটি অবস্থানে রাখা হয় যে পিভটের বামপাশের সব এলিমেন্ট পিভটের চেয়ে ছোট এবং ডানপাশের এলিমেন্ট পিভটের চেয়ে বড়। এরপর পুনরায় বাম ও ডান অংশে এই প্রক্রিয়া পুনরাবৃত্তি করা হয়।

সময় জটিলতা (Time Complexity): $O(n \log n)$ (সর্বোত্তম এবং গড় ক্ষেত্রে), $O(n^2)$ (খারাপ ক্ষেত্রে)

জাভায় কুইক সর্ট:

public class QuickSort {

    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // pi is partitioning index, arr[pi] is now at right place
            int pi = partition(arr, low, high);

            // Recursively sort the two halves
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    private static int partition(int[] arr, int low, int high) {
        // Pivot (Element to be placed at right position)
        int pivot = arr[high];
        int i = (low - 1); // Index of smaller element

        for (int j = low; j < high; j++) {
            // If current element is smaller than or equal to pivot
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i + 1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1;
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5};
        int n = arr.length;
        quickSort(arr, 0, n - 1);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

আউটপুট:

Sorted array: 
1 5 7 8 9 10 

সারাংশ

সর্টিং অ্যালগরিদমগুলি ডাটা স্ট্রাকচার এবং অ্যালগরিদমের একটি গুরুত্বপূর্ণ অংশ, যা ডাটা সাজানোর জন্য ব্যবহৃত হয়। এখানে আমরা পাঁচটি জনপ্রিয় সর্টিং অ্যালগরিদম আলোচনা করেছি: বাবল সর্ট (Bubble Sort), ইনসার্ট সর্ট (Insertion Sort), সিলেকশন সর্ট (Selection Sort), মার্জ সর্ট (Merge Sort), এবং কুইক সর্ট (Quick Sort)। এই অ্যালগরিদমগুলির মধ্যে কিছু সহজ, তবে কিছু জটিল, এবং তাদের সময় জটিলতা ও কার্যকারিতা পরিস্থিতি অনুযায়ী ভিন্ন হতে পারে।

Sorting হল ডাটা স্ট্রাকচার এবং অ্যালগরিদমের একটি গুরুত্বপূর্ণ প্রক্রিয়া, যেখানে একটি অর্ডারড সিকোয়েন্স তৈরি করা হয়। এটি এমন একটি প্রক্রিয়া যার মাধ্যমে অর্ডারহীন ডেটাকে একটি নির্দিষ্ট ক্রম অনুযায়ী সাজানো হয়। Sorting এর মাধ্যমে ডেটার মধ্যে সম্পর্ক তৈরি করা হয়, যাতে পরবর্তী কোন অপারেশন যেমন অনুসন্ধান বা বিশ্লেষণ আরও দ্রুত করা যায়। Sorting অ্যালগরিদম বিভিন্ন ক্ষেত্রে ব্যবহৃত হয়, যেমন ডাটা বিশ্লেষণ, ডেটাবেস ম্যানেজমেন্ট, ফাইল সিস্টেম, ইত্যাদি।

Sorting এর প্রয়োজনীয়তা:

• তথ্য অনুসন্ধান: Sorted ডেটা থাকার কারণে অনুসন্ধান প্রক্রিয়া অনেক দ্রুত হয়, বিশেষত Binary Search এর মতো অ্যালগরিদম ব্যবহার করার সময়।
• ডেটা বিশ্লেষণ: ডেটা সাজানো থাকলে তা পরবর্তী বিশ্লেষণের জন্য সুবিধাজনক হয়, যেমন রেঞ্জ কুয়েরি বা স্ট্যাটিস্টিক্স ক্যালকুলেশন।
• ডেটাবেস অপটিমাইজেশন: ডেটাবেসে ডেটা সাজানো থাকলে সার্চিং, ইনসার্ট এবং ডিলিট অপারেশন আরও কার্যকরী এবং দ্রুত হয়।
• কনটেন্ট সিকোয়েন্স: Sorting বিভিন্ন ধরনের ডেটা (যেমন নাম, তারিখ, সংখ্যা) একটি প্রাকৃতিক সিকোয়েন্স বা অর্ডারে সাজাতে সাহায্য করে।

1. Sorting এর মৌলিক ধারণা

Sorting হল একটি প্রক্রিয়া যেখানে ডেটার তালিকাকে ascending (বৃদ্ধি) বা descending (হ্রাস) ক্রমে সাজানো হয়। এটি সাধারণত নিম্নলিখিত ধাপগুলোতে সম্পন্ন করা হয়:

1. তালিকার উপাদানগুলোর মধ্যে তুলনা করা: দুইটি উপাদানকে তুলনা করা হয়।
2. যতক্ষণ না সঠিক ক্রম পাওয়া যায় ততক্ষণ পুনরাবৃত্তি করা: উপাদানগুলোকে একে অপরের সাথে তুলনা করে উপযুক্ত ক্রমে সাজানো হয়।

2. Sorting অ্যালগরিদমের প্রকারভেদ

Java তে ডেটা সাজানোর জন্য বিভিন্ন ধরনের sorting algorithm রয়েছে। কিছু জনপ্রিয় sorting অ্যালগরিদমের মধ্যে রয়েছে:

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort

প্রত্যেকটি sorting অ্যালগরিদমের নিজস্ব গতি এবং কার্যকারিতা রয়েছে, এবং এগুলোর পারফরম্যান্স ডেটার আকার এবং সাজানোর পদ্ধতির উপর নির্ভর করে।

3. Sorting এর অ্যালগরিদম গুলি

3.1 Bubble Sort

Bubble Sort হল একটি সহজ এবং প্রাথমিক sorting অ্যালগরিদম। এটি সাদৃশ্যভাবে কাজ করে: তালিকার উপাদানগুলো একে একে তুলনা করা হয় এবং সেগুলোকে সঠিক ক্রমে রাখার জন্য একে অপরের সাথে "বাবল" করা হয়।

উদাহরণ:

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

ব্যাখ্যা:

• Time Complexity: O(n^2) - Worst, Best, and Average Case।
• এটি সাদৃশ্যভাবে সহজ, তবে বৃহৎ ডেটার জন্য এটি অল্প কার্যকরী হতে পারে।

3.2 Selection Sort

Selection Sort হল একটি আরেকটি সহজ অ্যালগরিদম যা একটি তালিকা থেকে সবচেয়ে ছোট উপাদানটি নির্বাচন করে এবং তা সঠিক অবস্থানে রাখে। এরপর বাকি অংশের জন্য এটি পুনরাবৃত্তি হয়।

উদাহরণ:

public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

ব্যাখ্যা:

• Time Complexity: O(n^2) - Worst, Best, and Average Case।
• এটি মোটামুটি সহজ, তবে বিশাল তালিকার জন্য কার্যকরী নয়।

3.3 Insertion Sort

Insertion Sort একটি প্রাথমিক sorting অ্যালগরিদম যেখানে প্রতিটি উপাদানকে সঠিক জায়গায় ইনসার্ট করা হয়। এটি কাজ করে একটি তালিকা থেকে একে একে উপাদান নিয়ে, সেগুলোকে সঠিক স্থানে স্থানান্তর করে।

উদাহরণ:

public class InsertionSort {
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6};
        insertionSort(arr);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

ব্যাখ্যা:

• Time Complexity: O(n^2) - Worst Case, O(n) Best Case।
• এটি ছোট তালিকার জন্য কার্যকরী, তবে বৃহৎ তালিকায় ধীর হতে পারে।

3.4 Merge Sort

Merge Sort হল একটি Divide and Conquer অ্যালগরিদম যা তালিকাকে ভাগ করে এবং পরে প্রতিটি ভাগ মিশিয়ে সঠিকভাবে সাজায়। এটি দ্রুত এবং কার্যকরী হয়, বিশেষত বড় তালিকাগুলোর জন্য।

উদাহরণ:

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;

            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);
            merge(arr, left, middle, right);
        }
    }

    public static void merge(int[] arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArr = new int[n1];
        int[] rightArr = new int[n2];

        for (int i = 0; i < n1; i++) leftArr[i] = arr[left + i];
        for (int i = 0; i < n2; i++) rightArr[i] = arr[middle + 1 + i];

        int i = 0, j = 0;
        int k = left;

        while (i < n1 && j < n2) {
            if (leftArr[i] <= rightArr[j]) {
                arr[k] = leftArr[i];
                i++;
            } else {
                arr[k] = rightArr[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = leftArr[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArr[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        mergeSort(arr, 0, arr.length - 1);
        System.out.println("Sorted array: ");
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

ব্যাখ্যা:

• Time Complexity: O(n log n) - Worst, Best, and Average Case।
• এটি একটি Divide and Conquer অ্যালগরিদম, যা বৃহৎ তালিকা দ্রুত সাজানোর জন্য খুবই কার্যকরী।

4. Sorting অ্যালগরিদমের প্রয়োজনীয়তা

Sorting অ্যালগরিদমের প্রধান প্রয়োজনীয়তা গুলি:

1. ডাটা অনুসন্ধান: সাজানো ডেটার মধ্যে দ্রুত অনুসন্ধান করা সম্ভব হয়। যেমন Binary Search।
2. অ্যালগরিদমের উন্নত কার্যকারিতা: অনেক অ্যালগরিদম যেমন Heap Sort, Merge Sort দ্রুত এবং কার্যকরী হতে পারে।
3. ডেটাবেস এবং ফাইল সিস্টেম: ডেটাবেসে দ্রুত অনুসন্ধান এবং আপডেট করার জন্য ডেটা সাজানো থাকে।
4. অপটিমাইজেশন: অনেক ক্ষেত্রে ডেটা সঠিকভাবে সাজিয়ে দিলে পরবর্তী কাজগুলো দ্রুত সম্পন্ন হয়।

Sorting একটি অত্যন্ত গুরুত্বপূর্ণ প্রক্রিয়া ডাটা স্ট্রাকচার এবং অ্যালগরিদমে, যা বিভিন্ন ডেটা অপারেশন যেমন অনুসন্ধান, বিশ্লেষণ এবং অপটিমাইজেশনে সাহায্য করে। Bubble Sort, Selection Sort, Merge Sort, এবং অন্যান্য

sorting অ্যালগরিদমগুলির মাধ্যমে ডেটা সাজানো হয়, এবং এগুলি বিভিন্ন পরিস্থিতিতে কার্যকরী হয়। আপনার প্রয়োজন এবং ডেটার আকার অনুযায়ী সঠিক sorting অ্যালগরিদম নির্বাচন করা খুবই গুরুত্বপূর্ণ।

1. Bubble Sort

Bubble Sort একটি সরল অ্যালগরিদম যা ধারাবাহিকভাবে তালিকার দুটিAdjacent উপাদান তুলনা করে তাদের সঠিক অর্ডারে সোয়ারাপ (swap) করে। এটি প্রতিটি পাসে বৃহত্তম বা ছোটতম উপাদানটি সঠিক স্থানে নিয়ে আসে, যেমন বুদ্বুদ একে অপরের সাথে উঠে আসে (তাই এর নাম 'Bubble Sort')।

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n) (যখন তালিকা ইতিমধ্যেই সজ্জিত থাকে)
• Space Complexity: O(1)

Bubble Sort Implementation:

public class BubbleSort {
    // Method to perform Bubble Sort
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        boolean swapped;
        
        // Traverse through all array elements
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            // Last i elements are already sorted, so skip them
            for (int j = 0; j < n - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // If no two elements were swapped by inner loop, the array is already sorted
            if (!swapped) {
                break;
            }
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Unsorted Array:");
        printArray(arr);

        bubbleSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);  // Output: 11 12 22 25 34 64 90
    }
}

ব্যাখ্যা:

• Bubble Sort প্রতিটি পাসে সর্বোচ্চ উপাদানটি সঠিক স্থানে নিয়ে আসে।
• যদি কোনো ইটারেশনে কোনো সোয়ারাপ না ঘটে, তবে এটি নিশ্চিত করে যে অ্যারে ইতিমধ্যেই সজ্জিত এবং প্রোগ্রামটি তাড়াতাড়ি থেমে যাবে (যা best case O(n) প্রদান করে)।

2. Selection Sort

Selection Sort হল একটি সোজা এবং সহজ অ্যালগরিদম যা তালিকা থেকে প্রতিবার সর্বনিম্ন (বা সর্বোচ্চ) উপাদান খুঁজে বের করে এবং তাকে সঠিক স্থানে স্থানান্তরিত করে।

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n²)
• Space Complexity: O(1)

Selection Sort Implementation:

public class SelectionSort {
    // Method to perform Selection Sort
    public static void selectionSort(int[] arr) {
        int n = arr.length;

        // Traverse through all array elements
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in the unsorted part
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }

            // Swap the found minimum element with the first element
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Unsorted Array:");
        printArray(arr);

        selectionSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);  // Output: 11 12 22 25 34 64 90
    }
}

ব্যাখ্যা:

• Selection Sort প্রতিটি ধাপে একটি উপাদান খুঁজে বের করে এবং সেটি তালিকার প্রথম অবস্থানে রেখে দেয়।
• এটি সর্বনিম্ন উপাদান খুঁজে পাওয়ার জন্য O(n²) সময় নেয়, তাই এটি ধীরগতি সম্পন্ন অ্যালগরিদম।

3. Insertion Sort

Insertion Sort হল একটি সরল অ্যালগরিদম যা তালিকার এক এক করে উপাদানগুলোকে একটি সাজানো অংশে সন্নিবেশ করে। এটি খুব সহজ কিন্তু ছোট আকারের তালিকার জন্য দ্রুত কাজ করে।

Time Complexity:

• Worst Case: O(n²)
• Best Case: O(n) (যখন তালিকা ইতিমধ্যে সজ্জিত থাকে)
• Space Complexity: O(1)

Insertion Sort Implementation:

public class InsertionSort {
    // Method to perform Insertion Sort
    public static void insertionSort(int[] arr) {
        int n = arr.length;

        // Traverse through 1 to n
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            // Move elements of arr[0..i-1] that are greater than key
            // to one position ahead of their current position
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j = j - 1;
            }

            arr[j + 1] = key;
        }
    }

    // Method to print the array
    public static void printArray(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        System.out.println("Unsorted Array:");
        printArray(arr);

        insertionSort(arr);

        System.out.println("Sorted Array:");
        printArray(arr);  // Output: 11 12 22 25 34 64 90
    }
}

ব্যাখ্যা:

• Insertion Sort প্রতিটি উপাদানকে সঠিক জায়গায় সন্নিবেশ করিয়ে দেয়।
• এটি যেমন ছোট তালিকার জন্য উপযোগী, তেমনি ইতিমধ্যেই সজ্জিত তালিকার জন্যও দ্রুত (O(n) সময়) কাজ করে।
• Worst Case (যখন তালিকা উল্টোভাবে সজ্জিত থাকে) এর সময় O(n²) হয়।

তুলনা: Bubble Sort, Selection Sort, এবং Insertion Sort

সারাংশ

• Bubble Sort, Selection Sort, এবং Insertion Sort হল বেসিক, সহজ এবং সরল comparison-based sorting algorithms।
• এগুলির Time Complexity সাধারণত O(n²), তবে কিছু ক্ষেত্রে যেমন ইতিমধ্যে সজ্জিত তালিকা, এগুলি আরো কার্যকরী হতে পারে (যেমন Insertion Sort-এর জন্য O(n) best case)।
• Bubble Sort এবং Insertion Sort স্টেবল (Stable) হয়, অর্থাৎ তারা সমান উপাদানগুলিকে তাদের আসল অর্ডারে রেখে দেয়, তবে Selection Sort সাধারণত unstable হয়।
• ছোট আকারের তালিকার জন্য এই অ্যালগরিদমগুলি কার্যকরী, তবে বড় তালিকাগুলির জন্য দ্রুত অ্যালগরিদম (যেমন Merge Sort, Quick Sort) ব্যবহার করা উচিত।

Merge Sort এবং Quick Sort হল দুটি জনপ্রিয় এবং কার্যকরী divide-and-conquer অ্যালগরিদম, যা ডাটা সোর্টিং করতে ব্যবহৃত হয়। এই দুটি অ্যালগরিদম বিভিন্ন পদ্ধতিতে কাজ করে এবং প্রতিটি অ্যালগরিদমের কিছু শক্তি এবং দুর্বলতা রয়েছে। এখানে আমরা Merge Sort এবং Quick Sort এর কার্যপ্রণালী, বৈশিষ্ট্য, এবং Java তে তাদের বাস্তবায়ন নিয়ে আলোচনা করব।

1. Merge Sort

Merge Sort হল একটি ডিভাইড-এন্ড-কনকার অ্যালগরিদম যা divide-and-conquer পদ্ধতি ব্যবহার করে একটি অ্যারে বা তালিকাকে সজ্জিত করতে সাহায্য করে। এটি একটি stable sort এবং O(n log n) টাইম কমপ্লেক্সিটি সহ একটি নির্ভরযোগ্য সোর্টিং অ্যালগরিদম।

1.1. Merge Sort Algorithm

1. Divide: একটি অ্যারে বা তালিকাকে দুইটি ভাগে বিভক্ত করুন যতক্ষণ না প্রতিটি সাব-অ্যারেতে একক উপাদান থাকে।
2. Conquer: প্রত্যেকটি সাব-অ্যারেকে সজ্জিত করুন। একটি অ্যারে দুটি ছোট অ্যারেতে বিভক্ত হয়ে যায় এবং পুনরাবৃত্তি অব্যাহত থাকে।
3. Combine: দুটি সাজানো অ্যারে একত্রিত করুন এবং তাদের একত্রিত করলে একটি সাজানো অ্যারে পাওয়া যায়।

1.2. Merge Sort Example in Java

import java.util.Arrays;

public class MergeSort {
    
    // Merge Sort Function
    public static void mergeSort(int[] array) {
        if (array.length < 2) return;  // Base case, array is already sorted
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);  // Left subarray
        int[] right = Arrays.copyOfRange(array, mid, array.length);  // Right subarray
        
        mergeSort(left);   // Recursively sort the left subarray
        mergeSort(right);  // Recursively sort the right subarray
        
        merge(array, left, right);  // Merge the two sorted subarrays
    }

    // Merge two sorted subarrays
    private static void merge(int[] array, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                array[k++] = left[i++];
            } else {
                array[k++] = right[j++];
            }
        }
        
        // Copy remaining elements of left array
        while (i < left.length) {
            array[k++] = left[i++];
        }
        
        // Copy remaining elements of right array
        while (j < right.length) {
            array[k++] = right[j++];
        }
    }

    // Main method to test MergeSort
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before Sorting: " + Arrays.toString(array));
        mergeSort(array);
        System.out.println("After Sorting: " + Arrays.toString(array));
    }
}

ব্যাখ্যা:

• mergeSort(): অ্যারেটি রিকার্সিভভাবে বিভক্ত করার জন্য ব্যবহৃত হচ্ছে।
• merge(): দুইটি সাজানো সাব-অ্যারেকে একত্রিত করার জন্য ব্যবহৃত হচ্ছে।

আউটপুট:

Before Sorting: [38, 27, 43, 3, 9, 82, 10]
After Sorting: [3, 9, 10, 27, 38, 43, 82]

সময় জটিলতা:

• Worst Case: O(n log n)
• Best Case: O(n log n)
• Average Case: O(n log n)

2. Quick Sort

Quick Sort একটি অন্যরকম divide-and-conquer অ্যালগরিদম, যা pivot উপাদান নির্বাচন করে এবং ডাটা সেই pivot এর তুলনায় ছোট এবং বড় অংশে ভাগ করে দেয়। এটি একটি অস্থির অ্যালগরিদম এবং প্রায়ই কার্যকরী হয়, তবে সঠিক pivot নির্বাচন করা খুবই গুরুত্বপূর্ণ।

2.1. Quick Sort Algorithm

1. Pivot Selection: একটি pivot নির্বাচন করুন।
2. Partition: ডাটা দুটি ভাগে বিভক্ত করুন যেখানে একটি ভাগের উপাদানগুলির মান pivot এর চেয়ে ছোট, এবং অন্যটি pivot এর চেয়ে বড়।
3. Recur: প্রতিটি ভাগে QuickSort প্রয়োগ করুন।
4. Base Case: যদি সাব-অ্যারের আকার ১ বা ০ হয়, তাহলে পুনরাবৃত্তি বন্ধ করুন।

2.2. Quick Sort Example in Java

import java.util.Arrays;

public class QuickSort {

    // QuickSort function
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);  // Recursively sort the left subarray
            quickSort(array, pivotIndex + 1, high); // Recursively sort the right subarray
        }
    }

    // Partition function
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];  // Choosing the last element as pivot
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                // Swap elements
                int temp = array[i];
                array[i] = array[j];
                array[j] = temp;
            }
        }

        // Swap the pivot element with the element at i + 1
        int temp = array[i + 1];
        array[i + 1] = array[high];
        array[high] = temp;

        return i + 1;
    }

    // Main method to test QuickSort
    public static void main(String[] args) {
        int[] array = {38, 27, 43, 3, 9, 82, 10};
        System.out.println("Before Sorting: " + Arrays.toString(array));
        quickSort(array, 0, array.length - 1);
        System.out.println("After Sorting: " + Arrays.toString(array));
    }
}

ব্যাখ্যা:

• quickSort(): রিকার্সিভভাবে সাব-অ্যারে সেগুলির জন্য QuickSort প্রয়োগ করা হচ্ছে।
• partition(): একটি pivot নির্বাচন করে, এবং ছোট ও বড় উপাদানগুলি বিভক্ত করা হচ্ছে।

আউটপুট:

Before Sorting: [38, 27, 43, 3, 9, 82, 10]
After Sorting: [3, 9, 10, 27, 38, 43, 82]

সময় জটিলতা:

• Worst Case: O(n²) (যখন প্রতিবার খারাপ pivot নির্বাচন করা হয়)
• Best Case: O(n log n) (যখন pivot খুব ভালোভাবে নির্বাচন করা হয়)
• Average Case: O(n log n)

3. Merge Sort vs Quick Sort

সারাংশ

• Merge Sort: এটি একটি divide-and-conquer অ্যালগরিদম, যেখানে ডাটা দুইটি ভাগে বিভক্ত করে এবং তাদের একত্রিত (merge) করা হয়। এটি একটি stable sort এবং O(n log n) টাইম কমপ্লেক্সিটি রাখে, তবে এটি অতিরিক্ত O(n) স্পেস ব্যবহার করে।
• Quick Sort: এটি একটি divide-and-conquer অ্যালগরিদম যা pivot নির্বাচন করে ডাটাকে ছোট এবং বড় অংশে ভাগ করে দেয়। এটি সাধারণত O(n log n) সময়ে কাজ করে, তবে খারাপ pivot নির্বাচন করলে এর O(n²) টাইম কমপ্লেক্সিটি হতে পারে।

যেহেতু Quick Sort সাধারণত দ্রুততর হয় এবং in-place সোর্টিং করে, এটি সাধারণত ছোট এবং মাঝারি আকারের ডেটাসেটের জন্য ব্যবহৃত হয়, যেখানে Merge Sort ব্যবহার করা হয় বড় ডেটাসেটের জন্য বা যখন stability প্রয়োজন হয়।

Counting Sort, Radix Sort, এবং Bucket Sort হল non-comparison-based sorting algorithms। এই অ্যালগরিদমগুলি O(n) টাইম কমপ্লেক্সিটিতে কাজ করতে সক্ষম, যেখানে n হল উপাদান সংখ্যা। এগুলি তুলনামূলকভাবে দ্রুত হতে পারে যখন ডাটা নির্দিষ্ট সীমার মধ্যে থাকে। এই গাইডে, আমরা প্রতিটি অ্যালগরিদমের কাজের প্রক্রিয়া এবং জাভাতে তাদের বাস্তবায়ন নিয়ে আলোচনা করব।

1. Counting Sort

Counting Sort একটি স্থির সংখ্যা (integers) ভিত্তিক সোর্টিং অ্যালগরিদম। এটি একটি অতিরিক্ত অ্যারে ব্যবহার করে যাতে প্রতিটি সম্ভাব্য মানের গণনা রাখা হয় এবং তারপর সেই গুণগত সংখ্যাগুলি ব্যবহার করে সঠিকভাবে ডাটা সাজানো হয়। Counting Sort শুধুমাত্র তখন কার্যকরী যখন ইনপুট ডাটার পরিসীমা (range) সীমিত হয় এবং তা ইন্টিজার হতে হবে।

1.1. Counting Sort Algorithm Steps

1. Count the frequency of each element in the input array.
2. Modify the count array by adding each element's frequency with the sum of the previous counts.
3. Place elements in the output array based on their frequencies.

1.2. Counting Sort in Java

import java.util.Arrays;

public class CountingSort {

    public void countingSort(int[] arr) {
        int n = arr.length;

        // Find the maximum element in the array
        int max = Arrays.stream(arr).max().getAsInt();

        // Create count array and initialize with 0
        int[] count = new int[max + 1];

        // Count the frequency of each element
        for (int i = 0; i < n; i++) {
            count[arr[i]]++;
        }

        // Update the count array to contain the actual position of each element
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }

        // Output array to store the sorted elements
        int[] output = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }

        // Copy the sorted array to the original array
        System.arraycopy(output, 0, arr, 0, n);
    }

    // Utility function to print the array
    public void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        CountingSort sorter = new CountingSort();
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        
        System.out.println("Original Array:");
        sorter.printArray(arr);
        
        sorter.countingSort(arr);
        
        System.out.println("Sorted Array:");
        sorter.printArray(arr);  // Output: 1 2 2 3 3 4 8
    }
}

1.3. Explanation:

• Step 1: আমরা ইনপুট অ্যারেতে প্রতিটি সংখ্যার ফ্রিকোয়েন্সি হিসাব করি।
• Step 2: Count array আপডেট করা হয় যাতে এতে প্রতিটি উপাদানের সঠিক অবস্থান পাওয়া যায়।
• Step 3: সঠিক স্থানে উপাদানগুলি output array তে রাখার পর, আমরা সেগুলি মূল অ্যারে তে কপি করি।

2. Radix Sort

Radix Sort একটি ডিজিট ভিত্তিক সোর্টিং অ্যালগরিদম যা সংখ্যাগুলির প্রতিটি ডিজিট নিয়ে কাজ করে। এটি LSD (Least Significant Digit) বা MSD (Most Significant Digit) পদ্ধতিতে কাজ করতে পারে, তবে সাধারণত LSD পদ্ধতি বেশি ব্যবহৃত হয়।

2.1. Radix Sort Algorithm Steps

1. Sort the elements based on the least significant digit (LSD) first.
2. Move to the next digit and sort the elements again.
3. Repeat this process for all the digits (until the largest digit's place).

2.2. Radix Sort in Java

import java.util.Arrays;

public class RadixSort {

    // Function to perform counting sort on the basis of digit
    private void countingSort(int[] arr, int exp) {
        int n = arr.length;
        int[] output = new int[n];
        int[] count = new int[10]; // Counting digits from 0 to 9

        // Store count of occurrences in count[]
        for (int i = 0; i < n; i++) {
            count[(arr[i] / exp) % 10]++;
        }

        // Change count[i] so that count[i] now contains actual position of this digit in output[]
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // Build the output array
        for (int i = n - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        // Copy the output array to arr[], so that arr[] now contains sorted numbers based on current digit
        System.arraycopy(output, 0, arr, 0, n);
    }

    // Function to perform radix sort
    public void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();

        // Perform counting sort for every digit. The exp is 10^i where i is current digit number
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    // Utility function to print the array
    public void printArray(int[] arr) {
        for (int num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        RadixSort sorter = new RadixSort();
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        
        System.out.println("Original Array:");
        sorter.printArray(arr);
        
        sorter.radixSort(arr);
        
        System.out.println("Sorted Array:");
        sorter.printArray(arr);  // Output: 2 24 45 66 75 90 170 802
    }
}

2.3. Explanation:

• Counting Sort is applied to each digit of the numbers in increasing significance (LSD).
• We start from the least significant digit and move towards the most significant digit.
• At each step, the array is sorted based on the current digit, and this process continues for all digits.

3. Bucket Sort

Bucket Sort একটি ডিস্ট্রিবিউশন ভিত্তিক অ্যালগরিদম যা ইনপুট ডাটাকে ছোট buckets (বালতিতে) ভাগ করে এবং পরে প্রতিটি বালতিতে আলাদাভাবে সোর্টিং করে।

3.1. Bucket Sort Algorithm Steps

1. Create buckets: Input array-এর উপাদানগুলিকে বিভিন্ন বালতিতে ভাগ করুন।
2. Sort the buckets: প্রতিটি বালতিকে আলাদাভাবে সোর্ট করুন।
3. Concatenate the results: সব বালতি একত্রিত করে সঠিকভাবে সাজানো অ্যারে তৈরি করুন।

3.2. Bucket Sort in Java

import java.util.*;

public class BucketSort {

    public void bucketSort(float[] arr) {
        // 1. Create an array of empty buckets
        int n = arr.length;
        if (n <= 0) return;

        @SuppressWarnings("unchecked")
        List<Float>[] buckets = new List[n];

        // 2. Put elements into different buckets
        for (int i = 0; i < n; i++) {
            int index = (int) (n * arr[i]);  // Get the index of the bucket
            if (buckets[index] == null) {
                buckets[index] = new ArrayList<>();
            }
            buckets[index].add(arr[i]);
        }

        // 3. Sort each bucket and concatenate the results
        int k = 0;
        for (int i = 0; i < n; i++) {
            if (buckets[i] != null) {
                Collections.sort(buckets[i]);
                for (float num : buckets[i]) {
                    arr[k++] = num;
                }
            }
        }
    }

    // Utility function to print the array
    public void printArray(float[] arr) {
        for (float num : arr) {
            System.out.print(num + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        BucketSort sorter = new BucketSort();
        float[] arr = {0.42f, 0.32f, 0.23f, 0.85f, 0.91f, 0.61f};

        System.out.println("Original Array:");
        sorter.printArray(arr);

        sorter.bucketSort(arr);

        System.out.println("Sorted Array:");
        sorter.printArray(arr);  // Output: 0.23 0.32 0.42 0.61 0.85 0.91
    }
}

3.3. Explanation:

• Bucket Sort প্রথমে উপাদানগুলোকে বিভিন্ন বালতিতে বিভক্ত করে, তারপর প্রতিটি বালতিকে সোর্ট করে এবং সবার শেষে বালতিগুলি একত্রিত করে একটি সাজানো অ্যারে তৈরি করে।
• Bucket Sort অ্যালগরিদমটি বিশেষভাবে উপকারী যখন উপাদানগুলো অনেকটা সমানভাবে বিতরিত থাকে।

সারাংশ

Counting Sort, Radix Sort, এবং Bucket Sort হল non-comparison-based sorting algorithms যা বিভিন্ন সমস্যা সমাধান করতে ব্যবহার করা হয়। Counting Sort ইন্টিজার এবং সীমিত পরিসরের ডাটার জন্য উপযোগী, Radix Sort সংখ্যার ডিজিট ভিত্তিক সোর্টিং এবং Bucket Sort সাধারণত ধারাবাহিক বা সরল সংখ্যা সংগ্রহের জন্য ভাল কাজ করে। এই তিনটি অ্যালগরিদমের মধ্যে Bucket Sort এবং Radix Sort সাধারণত O(n) টাইম কমপ্লেক্সিটিতে কাজ করতে পারে, যখন Counting Sort একটি নির্দিষ্ট সীমার মধ্যে কার্যকরী হয়।